한국정보통신학회 논문지 (Journal of the Korea Institute of Information and Communication Engineering)
Current Result Document :
| 한글제목(Korean Title) |
일배체형 추론을 위한 후보군 간소화 알고리즘 |
| 영문제목(English Title) |
A New Algorithm of Reducing Candidate Haplotypes for Haplotype Inference |
| 저자(Author) |
최문호
강승호
임형석
Mun-Ho Choi
Seung-Ho Kang
Hyeong-Seok Lim
|
| 원문수록처(Citation) |
VOL 17 NO. 07 PP. 1732 ~ 1739 (2013. 07) |
한글내용
(Korean Abstract) |
인간의 한쪽 염색체상에 나타나는 SNP의 서열인 일배체형을 식별해내면 효과적인 유전질병 연관검사를 할 수 있다. 일배체형 추론문제란 특정 집단의 유전자형 집합으로부터 집단에 속한 각 개체의 유전자형을 설명할 수 있는 일배체형 집합을 도출해내는 것을 말한다. 본 논문에서는 검약기반 일배체형 추론 문제에 대해 최종 결과에 기여하지 않는 일배체형 집합을 후보군에서 제외함으로써 일배체형 추론과정에서 탐색해야 할 후보 일배체형의 개수를 줄이는 사전처리 알고리즘을 제시한다. 제시된 알고리즘은 기존의 사전처리 알고리즘에 비해 매우 빠르게 수행되며, 제시된 사전처리 알고리즘의 결과를 적용한 일배체형 추론은 대다수의 경우에 최적해를 산출하고, 최적해를 산출하지 않는 경우에도 최적해의 일배체형 개수와 크게 차이나지 않음을 실험을 통해서 보인다.
|
영문내용
(English Abstract) |
The identification of haplotypes, which encode SNPs in a single chromosome, makes it possible to perform a haplotype-based association test with diseases. Given a set of genotypes from a population, the process of recovering the haplotypes that explain the genotypes is called haplotype inference. We propose a new preprocessing algorithm for the haplotype inference by pure parsimony (HIPP). The proposed algorithm excludes a large amount of redundant candidate haplotypes by detecting some groups of haplotypes that are dispensable for optimal solutions. For the well-known synthetic and biological data, the experimental results of our method show that our method run much faster than other preprocessing methods. After applying our preprocessing results, the numbers of haplotypes of HIPP solvers are equal to or slightly larger than that of optimal solutions.
|
| 키워드(Keyword) |
배체형 추론
검약기반
사전처리
일배체형 후보 간소화
Haplotype inference
Pure parsimony
Preprocessing
Reducing Candidate Haplotypes
|
| 파일첨부 |
PDF 다운로드
|
